package 剑指offer_leetcode;

/**
 * JZ19正则表达式匹配
 */
public class 剑指Offer19_正则表达式匹配 {
    public boolean isMatch(String s, String p) {
        int n1 = s.length();
        int n2 = p.length();
        boolean[][] dp = new boolean[n1+1][n2+1];
        for(int i=0;i<=n1;i++){
            for(int j=0;j<=n2;j++){
                if(j==0)
                    dp[i][j] = i==0?true:false;
                else{
                    if(p.charAt(j-1)!='*'){
                        if(i>0 && (p.charAt(j-1)==s.charAt(i-1) || p.charAt(j-1)=='.'))
                            dp[i][j] = dp[i-1][j-1];
                    }else{
                        if(j>=2)
                            dp[i][j] |= dp[i][j-2];
                        if(i>0 && j>=2 && (p.charAt(j-2)==s.charAt(i-1)||p.charAt(j-2)=='.'))
                            dp[i][j] |= dp[i-1][j];
                    }
                }
            }
        }
        return dp[n1][n2];
    }
}
